#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 1e5 + 5;

int n, m;

int f[N];
void init_f(int n) {
  f[1] = 0;
  rep(i, 2, n) f[i] = f[i >> 1] + 1;
}

ll mn[N][18];
void init_mn() {
  rep(i, 0, n - 1) cin >> mn[i][0];
  rep(j, 1, 16) {
    int len = 1 << j;
    rep(i, 0, n - len) mn[i][j] = min(mn[i][j - 1], mn[i + len / 2][j - 1]);
  }
}
ll get_mn(int l, int r) {
  int k = f[r + 1 - l];
  int len = 1 << k;
  return min(mn[l][k], mn[r + 1 - len][k]);
}

vector<int> g[N];
int dfn[N], cnt;
int mxd, dep[N], fa[N][18];
void init_tree() {
  rep(i, 2, n) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v), g[v].push_back(u);
  }
}
void dfs(int u, int fu) {
  dfn[u] = ++cnt;
  dep[u] = dep[fu] + 1;
  fa[u][0] = fu;
  rep(i, 1, 16) fa[u][i] = fa[fa[u][i - 1]][i - 1];
  for (int v : g[u]) {
    if (v == fu) continue;
    dfs(v, u);
  }
  g[u].clear();
}
int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  int d = dep[u] - dep[v];
  per(i, 16, 0) if (d & (1 << i)) u = fa[u][i];
  if (u == v) return u;
  per(i, 16, 0) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
  return fa[u][0];
}

vector<int> layers[N];
void init_layers() {
  mxd = *max_element(dep + 1, dep + n + 1);
  rep(i, 1, mxd) layers[i].clear();
  rep(i, 1, n) layers[dep[i]].push_back(i);
}

bool cmp(int x, int y) { return dfn[x] < dfn[y]; }
int st[N], top;
vector<int> virt[N];
void build_virt(int d) {
  vector<int>& layer = layers[d];
  sort(layer.begin(), layer.end(), cmp);
  st[top = 1] = 1;
  if (layer[0] != 1) st[++top] = layer[0];
  rep(i, 1, layer.size() - 1) {
    int x = lca(st[top], layer[i]);
    while (top > 1 && dep[st[top - 1]] >= dep[x])
      virt[st[top - 1]].push_back(st[top]), top--;
    if (x != st[top]) virt[x].push_back(st[top]), st[top] = x;
    st[++top] = layer[i];
  }
  // the final list
  while (top > 1) virt[st[top - 1]].push_back(st[top]), top--;
}
ll dp[N];
void dfs2(int u, int d) {
  if (dep[u] == d) {
    dp[u] = mn[0][0];
    return;
  }
  ll sum = 0;
  for (int v : virt[u]) {
    dfs2(v, d);
    ll now = dp[v];
    int d1 = dep[u] + 1, d2 = dep[v] - 1;
    if (d1 <= d2) now = min(now, get_mn(d - d2, d - d1));
    sum += now;
  }
  dp[u] = min(mn[d - dep[u]][0], sum);
  virt[u].clear();
}
void solve() {
  cin >> n;
  init_mn();
  init_tree();         // create tree
  cnt = 0, dfs(1, 0);  // get data && destroy tree
  init_layers();
  ll ans = 0;
  per(i, mxd, 1) {
    build_virt(i);
    dfs2(1, i);
    ans += dp[1];
  }
  cout << ans << endl;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  init_f(1e5);
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}